from typing import List

BASE = 97755331
MOD = 49999 ** 4 * 3 * 7


class Solution:
    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
        m = len(paths)

        paths = [tuple(path) for path in paths]

        left = 0
        right = min(len(path) for path in paths)

        while left < right:
            mid = (left + right + 1) // 2

            # ---------- 检查是否可行 ----------
            bucket = set()
            for i in range(m):
                hash_i = 0
                for j in range(mid):
                    hash_i = (hash_i * BASE + paths[i][j]) % MOD
                bucket_i = {hash_i}

                mult = pow(BASE, mid - 1, MOD)

                for j in range(mid,len(paths[i])):
                    hash_i = ((hash_i - paths[i][j-mid] * mult) * BASE + paths[i][j]) % MOD
                    bucket_i.add(hash_i)

                if i == 0:
                    bucket = bucket_i
                else:
                    bucket &= bucket_i

            if len(bucket) > 0:
                left = mid
            else:
                right = mid - 1

        return left


if __name__ == "__main__":
    # 2
    print(Solution().longestCommonSubpath(n=5, paths=[[0, 1, 2, 3, 4],
                                                      [2, 3, 4],
                                                      [4, 0, 1, 2, 3]]))

    # 0
    print(Solution().longestCommonSubpath(n=3, paths=[[0], [1], [2]]))

    # 1
    print(Solution().longestCommonSubpath(n=5, paths=[[0, 1, 2, 3, 4],
                                                      [4, 3, 2, 1, 0]]))
